#include "stdafx.h"
#include "CGreedy.h"
#include "include/tool.h"

#include <gtest/gtest.h>
#include <boost/numeric/ublas/matrix.hpp>
using namespace boost::numeric::ublas;

struct ACTIVITY {
    ACTIVITY(double ss, double ff) {
        s = ss; f = ff;
    }
    double s;
    double f;
};

int AsdpLookup(const std::vector<ACTIVITY> &A, matrix<int> &c, matrix<int> &b, int i, int j) {
    if (c(i, j) > -1) {
        return c(i, j);
    }

    int max = (-1)*std::numeric_limits<int>::max();
    c(i, j) = 0;
    for (int k = i+1; k <= j-1; ++k) {
        if (A[i].f <= A[k].s && A[k].f <= A[j].s) {
            int q = AsdpLookup(A, c, b, i, k) + AsdpLookup(A, c, b, k, j) + 1;
            if (c(i, j) < q) {
                c(i, j) = q;
                b(i, j) = k;
            }
        }
    }
    return c(i, j);
}

int ActivitySelectorDynamicProgram(const std::vector<ACTIVITY> &A, matrix<int> &c, matrix<int> &b) {
    for (int i = 0; i < c.size1(); ++i) {
        for (int j = 0; j < c.size2(); ++j) {
            c(i, j) = -1;
        }
    }

    for (int i = 0; i < c.size1(); ++i) {
        for (int j = 0; j < c.size2(); ++j) {
            b(i, j) = 0;
        }
    }

    return AsdpLookup(A, c, b, 0, A.size()-1);
}

void ActivitySelectorPrint(const std::vector<ACTIVITY> &A, const matrix<int> &b, int i, int j) {
    if (b(i, j)>0) {
        ActivitySelectorPrint(A, b, i, b(i, j));
        std::cout << "A[" << b(i, j) << "] ";
        ActivitySelectorPrint(A, b, b(i, j), j);
    }
}

CGreedy::CGreedy()
{
    //ctor
}

CGreedy::~CGreedy()
{
    //dtor
}
int CGreedy::run(void) {
    std::vector<ACTIVITY> A;
    A.push_back(ACTIVITY(-10, 0));
    A.push_back(ACTIVITY(1, 4));
    A.push_back(ACTIVITY(3, 5));
    A.push_back(ACTIVITY(0, 6));
    A.push_back(ACTIVITY(5, 7));
    A.push_back(ACTIVITY(3, 8));
    A.push_back(ACTIVITY(5, 9));
    A.push_back(ACTIVITY(6, 10));
    A.push_back(ACTIVITY(8, 11));
    A.push_back(ACTIVITY(8, 12));
    A.push_back(ACTIVITY(2, 13));
    A.push_back(ACTIVITY(12, 14));
    A.push_back(ACTIVITY(std::numeric_limits<int>::max(), std::numeric_limits<int>::max()));

    std::cout << "activity selector through dynamic programming :" << std::endl;
    matrix<int> c(A.size(), A.size()), b(A.size(), A.size());
    std::cout << "the big activity number is " << ActivitySelectorDynamicProgram(A, c, b) << std::endl;
    std::cout << "matrix c :" << std::endl;
    print_matrix(c, 4);
    std::cout << "matrix b :" << std::endl;
    print_matrix(b, 4);
    ActivitySelectorPrint(A, b, 0, A.size()-1);
    std::cout << std::endl;

    return 0;
}

TEST(CGreedy, run)
{
	CGreedy().run();
}
